1. Field of the Invention
The present invention relates to an image correlation calculation apparatus for optically calculating correlation between a reference pattern and an image such as a character or any other figure, the apparatus being suitably used in an image recognition apparatus such as an OCR (Optical Character Reader).
2. Description of the Prior Art
A conventional image recognition apparatus for recognizing an image such as a character or any other figure employs pattern matching between an input image to be recognized (an unknown pattern) and a reference pattern (a known pattern) as an image recognition technique. In this case, class classification of an input image is performed to determine which class is assigned to the input image, or similarity discrimination is performed to determine which reference pattern most resembles the input image, on the basis of the pattern matching results.
In the above pattern matching, correlation calculations as the basic means are performed by a correlation calculation apparatus. A typical example of the apparatus is a correlation calculation apparatus for digitally processing an input image by using mainly electronic techniques (to be referred to as a digital correlation calculation apparatus).
A typical conventional digital correlation calculation apparatus will be described hereinafter. An input image to be recognized is divided into a matrix of M x N picture elements corresponding to an orthogonal coordinate system, and these picture elements are binarized. The same processing as described above is performed for reference patterns, and each picture element is binarized. The input image and the reference patterns have binary image values corresponding to a large number of points in an orthogonal coordinate system.
The degree of correlation between the input image and the reference patterns is determined by a correlation function between the input image and the reference pattern. The correlation function is obtained in consideration of a positional error of the input image and a variety of formats (a handwritten or printed character, kinds of printing styles of penmanship, etc.) of the input image. The correlation function is derived by relatively shifting the origin of the input image to the origin of the reference pattern in such a manner that shifts of these origins are sequentially changed relative to each other, and by calculating the product of the corresponding image values of the input image and the reference pattern for every shift.
In the x-y coordinate system, when the functions of the input image and the reference pattern are defined as f(x,y) and g(x,y), respectively, and a relative shift of the input image and the reference pattern is defined as (x.sub.k,y.sub.l), a correlation value between the input image and the reference pattern is calculated as follows: ##EQU1## If k=1 to M and l=1 to N, then the correlation function can be obtained.
In such correlation calculations, if the input image f(x,y) resembles the reference pattern g(x,y), the resultant correlation value is large. If the reference pattern g(x,y) coincides with the input image f(x,y), an auto-correlation function is derived. Otherwise, a cross-correlation function is derived. Similar correlation calculations are performed for a large number of reference patterns. The correlation functions of the respective reference patterns are compared with each other or with a reference value, thereby discriminating the degree of similarity between the input image and the reference patterns.
The above correlation calculations in a general-purpose computer require a long period of time. For this reason, an image recognition correlation calculator is used in practice.
In order to perform image recognition, correlation calculations of a large number of reference patterns must be performed, and a very long processing time is required. In order to perform image recognition at a desirable practical rate, the correlation functions are determined by calculations of correlation values at several points in practice due to time limitations even if the image recognition correlation calculator is used. The degree of similarity is determined by comparing sums of the correlation values of the reference patterns.
A conventional optical pattern matching scheme for discriminating the degree of similarity between the input image and the reference patterns is also known instead of digital correlation calculations by a digital correlation calculation apparatus for pattern matching.
A conventional optical pattern matching scheme will be described below. An input image u(x,y) displayed on a display such as a CRT or the like is focused by an optical lens onto a reference mask having a reference pattern v(x,y). One of the input image and the reference mask, e.g., the reference mask is shifted by a shift (x.sub.0,y.sub.0), and the correlation values are obtained which are u(x,y) multiplied by v(x+x.sub.0, y+y.sub.0) When the shift (x.sub.0,y.sub.0)is continuously changed, a correlation function between the input image u(x,y) and the reference pattern v(x,y) is obtained.
According to the above optical pattern matching scheme, since the input image is directly formed on the reference pattern, the correlation value can be obtained by condensing the beam passing through the reference mask having the corresponding reference pattern. The correlation function between the input image and the reference pattern can be determined such that the one of input image and the reference pattern is moved to continuously change the relative shift and that the correlation value is obtained for every shift. The same processing described above is repeated for a large number of reference patterns to obtain the corresponding correlation functions. These correlation functions are compared with each other or with a reference value, and the degree of similarity between the input image and the reference patterns can be discriminated.
In the conventional optical pattern matching scheme described above, the correlation calculation time can be shortened as compared with the conventional digital processing utilizing the digital correlation calculation apparatus.
In the conventional schemes described, however, the following problems are posed by the digital correlation calculation apparatus and the optical pattern matching apparatus.
In the conventional digital correlation apparatus, digital processing for a large number of image values must be repeated to obtain desired discrimination precision. The number of calculations is increased to prolong the processing time. In particular, in order to recognize a two-dimensional image, the image must be read by a large number of image sensors, and identical operation must be repeated for a large number of pieces of image information from these image sensors. The number of calculations is thus further increased.
The above-mentioned correlation calculator is used to reduce the processing time in practice. Even in this case, the correlation function between the input image and the reference patterns is determined by calculations of correlation values at limited several points due to time limitations. For this reason, precision of similarity discrimination is undesirably degraded.
In the conventional optical pattern matching apparatus, processing time of correlation calculations can be shortened comparatively. However, in this case, the correlation values must be calculated by repeatedly comparing the input image with a large number of reference patterns. the processing time cannot therefore be greatly reduced. In addition, in order to obtain the correlation function between the input image and the reference pattern, at least one of these is continuously shifted to obtain a large number correlation values. These values are used to calculate a correlation function, thus still requiring a considerably long period of time.